package com.lans.graph;

import com.lans.linear.Queue;

import java.util.LinkedList;

/**
 * @author: lans
 * @date: 2025/3/9
 * @name: 刘宇
 * 广度优先遍历
 */
public class BreadthFirstSearch {

    private boolean[] marked;

    private int count;

    private Queue<Integer> waitSearch;

    public BreadthFirstSearch(Graph G,int s) {
        marked = new boolean[G.V()];
        waitSearch = new Queue<Integer>();
        bfs(G,s);
    }

    //广度优先遍历
    private void bfs(Graph G,int v) {
        marked[v] = true;
        //放入待搜索的队列中去
        waitSearch.enqueue(v);
        while(!waitSearch.isEmpty()){
            Integer wait= waitSearch.dequeue();
            for(Integer w:G.adj(wait)){
                if(!marked[w]){
                    bfs(G,w);
                }
            }
        }
        count++;
    }

    public boolean marked(int w){
        return marked[w];
    }
    public int getCount(){
        return count;
    }
}